R Notebook
This notebook describes implementation of the Boruta permutations method to identify consensus features from the TARGET pediatric AMl dataset.
Methods
We applied Boruta as implemented in the Boruta R package (v.6.0.0). We implemented the Boruta permuataions method with a consensus rank importance metric, and conducted bootstraps of data subset selection (2/3rds of data, to simulate iteratively redraw of training sample subset). Each Boruta iteration was allowed to run for up to 100 steps, over which the algorithm designated “confirmed”, “tentative”, and “rejected” features.
Hyperparameter sets used for algorithm with Boruta permuatations were informed by preliminary investigation of model performances across hyperparameter sets for each algorithm. The initial defined training and test data subsets, as used to measure differential gene expression, were used in hyperparameter optimization and to derive the rank-based consensus importance measure as described below.
Consensus Importance (‘nrank’)
To calculate a consensus importance metric, we define a method to take the median normalized absolute rank of features from across 4 algorithms (lasso, XGBoost, Random Forest, and SVM).
Steps to calculate this normalized median importance include:
- Calculate algorithm-specific importances.
- Take absolute importances from (1).
- Calculate naive rank (index-based) of importances from (2).
- Calcualte normalized rank from (3).
- Calculate median normalized rank and return.
We settled on this strategy due to properties of Boruta and feature selection. For comparison, a standard of Boruta using Random Forest importance shows oscillation of shadow feature importances, gradual exclusion of rejected features, and retention of important features (Figure 1)
History of shadow feature importances over permuatations in a single Boruta iteration using Random Forest importance (green: confirmed features, red: rejected features, yellow: tentative features).
By contrast, using a naive median rank as our consensus importance yields a static pattern of shadow feature importance across permutations (Figure 2).
History of shadow feature importance over Boruta permutations using naive median rank as consensus importance (green: confirmed; red: rejected).
The static nature of naive rank is almost certainly due to immediate fixation of feature consensus importance from the first iteration. This is likely because naive rank is not normalized, and for penalized algorithms (XGBoost and lasso), it returns very low rank for most features. These characteristics make this metric less desriable for use in Boruta permutations, as importance estimation does not benefit from shadow feature importance and background estimation.
Using the steps described above, we calculated a normalized median rank for the consensus importance we ultimately used to identify consensus important features. A single Boruta iteration using this metric shows progressive retention of “confirmed” and “tentative” features, and loss of “rejected” features over permutations, indicating this metric does benefit from shadow feature iterations (Figure 3).
History of shadow feature importance with normalized median rank used to calculate consensus importance (green: confirmed; red: rejected; yellow: tentative)
Comparing consensus importance derived from naive median rank and normalized median rank directly, there is greater variation in importance measured using the latter (Figure 4).
Comparison of median rank measures (naive vs. normalized) across 4 algorithms (lasso: green, XGBoost: blue, Random Forest: orange, and SVM: red).
Bootstrapping Boruta Permutations
We performed 1000 bootstraps of Boruta permutations for each of five respective importance metrics. Each bootstrap redrew two thirds of the dataset, with preservation of sample group frequency to overall frequency. This was to simulate redrawing training data subsets. The importance metrics applied included:
- Consensus importance (normalized median absolute rank, see above).
- Lasso importance (Beta-value coefficient).
- XGBoost importance (feature importance).
- Random Forest Importance (feature importance).
- SVM Importance (feature weight).
Code for running bootstraps is described below.
Importance metric functions were defined as follows:
# Importance Functions
impLasso <- function(df, classes, trainindices, seed=2019){
# df : data frame to parse, rownames = classifier groupings, colnames = feature ids
require(glmnet)
require(SummarizedExperiment)
set.seed(seed)
var.classifier <- response <- as.character(classes)
y <- factor(response); names(y) <- rownames(df) # response var obj
x = df # genes of interest
contrast <- contrasts(y)
grid <- 10^ seq(10,-2, length=100)
# use cross-validation on the training model.CV only for lambda
message("performing cross-validation...")
cv.fit <- cv.glmnet(x[trainindices,], y[trainindices], family = "binomial",
type.logistic="modified.Newton", standardize = FALSE,
lambda = grid, alpha=1, nfolds = length(trainindices), #LOOCV
type.measure = "class", intercept = FALSE)
#Select lambda min.
message("selecting lambda min...")
lambda.min <- cv.fit$lambda.min
#Fit the full dataset.
message("fitting whole dataset")
lassofit <- glmnet(x, y, family = "binomial", standardize = FALSE,
lambda = grid, alpha = 1, intercept = FALSE)
#Extract the coefficients
lassoimp <- predict(lassofit, type="coefficients", s=lambda.min)
lassoimp <- lassoimp[2:nrow(lassoimp),1]
return(lassoimp)
}
impRF <- function(df, classes, ntrees=100, seed=2019){
require(randomForest)
set.seed(seed)
class <- as.numeric(classes)
rffit <- randomForest(class ~ ., data = as.matrix(df), ntree = ntrees,proximity = TRUE)
# rfimp <- as.numeric(getRFIvar(rfmodel=rffit))
rfimp <- importance(rffit)[,1]
return(rfimp)
}
impXGB <- function(df, classes, seed=2019){
require(xgboost)
set.seed(2019)
message("fitting xgboost model...")
xgbfit <- xgboost(data = df, label = classes, max_depth = 2,
eta = 1, nthread = 2, nrounds = 2, objective = "binary:logistic")
message("getting xgboost importances...")
xgbimp <- xgb.importance(feature_names = colnames(df), model = xgbfit)
message("reformatting xgb importances...")
xgbimp.format <- c(rep(0, ncol(df)))
names(xgbimp.format) <- colnames(df)
for(f in 1:nrow(xgbimp)){
xgbimp.format[which(colnames(df)==as.character(xgbimp[f,1]))] <- as.numeric(xgbimp[f,2])
}
xgbimp.format <- as.numeric(xgbimp.format)
names(xgbimp.format) <- colnames(df)
return(xgbimp.format)
}
impSVM <- function(df, classes, seed=2019){
require(e1071)
set.seed(2019)
message("fitting svm model...")
svmfit <- svm(as.factor(classes)~.,
data=df,
method="C-classification",
kernel="linear")
svmimp <- t(svmfit$coefs) %*% svmfit$SV
message("reformatting importances for output...")
svmimp.format <- svmimp[1,]
names(svmimp.format) <- colnames(svmimp)
return(svmimp.format)
}
# CML for Boruta Implementation
impBorutaCML <- function(x=x, y=y, seed, ranksummary="median",
algo.opt=c("lasso","rf","svm","xgb")){
# impCML
# Get consensus importance ranks from disparate algorithms.
# Arguments
# * df (matrix) : Entire dataset matrix (rows = instances, columns = features)
# * classes (character): categorizations of instances
# * algo.opt (list): List of valid algorithms to use for consensus
# * seed (int): Set the seed for reproducibility
# * ranksummary (string): Either "score", "median", or "mean", the operation used to calculate consensus rank.
# Returns:
# * Consensus rank, optionally a standard output table of importances for selected algorithms (if standtable==TRUE)
# define the test df if provided or if FALSE
df.test <- as.matrix(x)
message("proceeding with df of size ",nrow(df.test))
classes <- y
print("getting importances...")
implist <- list()
implabellist <- c()
if("lasso" %in% algo.opt){
# define the trainindices if none provided or FALSE
message("performing lasso...")
imp.lasso <- impLasso(df=as.matrix(df.test),
trainindices=seq(1,nrow(df.test)),
classes=classes)
implist[["lasso"]] <- imp.lasso
implabellist <- c(implabellist, "lasso")
}
if("rf" %in% algo.opt){
imp.rf <- impRF(df=as.matrix(df.test), classes=classes)
implist[["rf"]] <- imp.rf
implabellist <- c(implabellist, "rf")
}
if("xgb" %in% algo.opt){
imp.xgb <- impXGB(df=as.matrix(df.test), classes=classes)
implist[["xgb"]] <- imp.xgb
implabellist <- c(implabellist, "xgb")
}
if("svm" %in% algo.opt){
imp.svm <- impSVM(df=as.matrix(df.test), classes=classes)
implist[["svm"]] <- imp.svm
implabellist <- c(implabellist, "svm")
}
# match importance feature label ordering
if(length(implist)>1){
for(i in 1:(length(implist)-1)){
implist[[i]] <- implist[[i]][order(match(names(implist[[i]]),names(implist[[i+1]])))]
}
}
# get importance ranks and rankvars
if(ranksummary %in% c("median","mean")){
impranklist <- list()
# for each rank, calculate normalized rank position
message("computing normalized rank importances...")
for(i in 1:length(implist)){
algoname <- names(implist)[i]
impvals <- implist[[i]]
# naive rank
nranki <- rank(abs(impvals))
# adj1: compress rank lower bounds
min.ranki <- min(nranki)
nranki1 <- nranki
nranki1[nranki1==min.ranki] <- min(nranki1[!nranki1==min.ranki])-1
# adj2: normalize rank scale (dif.min/range)
nranki2 <- nranki1
nranki2 <- (nranki2-min(nranki2))/(max(nranki2)-min(nranki2))
# always compute absolute ranks
impranklist[[algoname]] <- nranki2
# plot(impvals, nranki, main=algoname)
# plot(impvals, nranki1, main=algoname)
# plot(impvals, nranki2, main=algoname)
}
medrank <- c()
meanrank <- c()
# iterate on features
for(r in 1:ncol(x)){
rvalr <- c() # get feature-level ranks
for(i in 1:length(impranklist)){
rvalr <- c(rvalr, impranklist[[i]][r]) # append ranks
}
# append summarized feature-level ranks, to return
medrank <- c(medrank, median(rvalr))
meanrank <- c(meanrank, mean(rvalr))
}
# final importance value is directly proportional to summarized rank
if(ranksummary=="median"){
lr <- medrank
} else{
lr <- meanrank
}
message("completed all tasks! Returning...")
lr
return(lr)
}
# get score importance metric
if(ranksummary=="score"){
# notes: by-algo score criteria
# lasso, coeff!=0
# rf, imp>=90th quantile
# svm, abs-weight >= 90th quantile
# xgb, coeff != 0
featnames <- colnames(x)
impscore <- rep(0,length(featnames))
names(impscore) <- colnames(x)
for(i in 1:length(implist)){
ni <- names(implist)[i]
if(ni=="lasso"){
which.features <- names(implist[[i]][implist[[i]]!=0])
impscore[which.features] <- impscore[which.features]+1
}
if(ni=="xgb"){
which.features <- names(implist[[i]][implist[[i]]!=0])
impscore[which.features] <- impscore[which.features]+1
}
if(ni=="rf"){
qrf <- as.numeric(quantile(as.numeric(implist[[i]]), seq(0,1,0.1))[10])
which.features <- names(implist[[i]][implist[[i]]>=qrf])
impscore[which.features] <- impscore[which.features]+1
}
if(ni=="svm"){
qsvm <- as.numeric(quantile(abs(as.numeric(implist[[i]])), seq(0,1,0.1))[10])
which.features <- names(implist[[i]][abs(implist[[i]])>=qsvm])
impscore[which.features] <- impscore[which.features]+1
}
}
rs <- as.numeric(impscore)
rs
return(rs)
}
return()
}
Results of Boruta Permutations Bootstraps
After performing bootstraps as described, we analyzed and summarized results.
Summaries Across Importance Functions
We observed the following results from each bootstrap iteration employing one of the five described importance measures.
## Feature Importance Histories Across Runs
Across bootstrap runs with varying importance metrics, we observed the following patterns of feature importnace histories from 4 bootstraps selected at random from each run.
Feature histories across Boruta permutations, from 4 bootstraps drawn at random from each of the 5 runs (green = confirmed, red = rejected, yellow = tentative, blue lines = shadow feature max, mean, and min).
Overlap of Confirmed Features
We also summarized the overlap in confirmed and recurrent confirmed features across bootstrap runs. The following upset plots show subset overlap membership for features confirmed at least once across bootstraps, greater that 5% of bootstraps, or greater than 20% of bootstraps.
Feature overlap among features confirmed in at least 1 bootstrap, across bootstrap runs with 5 importance metrics.
Feature overlap among features confirmed in at least 5% of bootstrap runs, across bootstrap runs with 5 importance metrics
Feature overlap among features confirmed in at least 20% of bootstrap runs, across bootstrap runs with 5 importance metrics
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayIKb3V0cHV0OgogIHBkZl9kb2N1bWVudDogZGVmYXVsdAogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKLS0tCgpUaGlzIG5vdGVib29rIGRlc2NyaWJlcyBpbXBsZW1lbnRhdGlvbiBvZiB0aGUgQm9ydXRhIHBlcm11dGF0aW9ucyBtZXRob2QgdG8gaWRlbnRpZnkgIGNvbnNlbnN1cyBmZWF0dXJlcyBmcm9tIHRoZSBUQVJHRVQgcGVkaWF0cmljIEFNbCBkYXRhc2V0LgoKIyBNZXRob2RzCgpXZSBhcHBsaWVkIEJvcnV0YSBhcyBpbXBsZW1lbnRlZCBpbiB0aGUgW0JvcnV0YV0oaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3BhY2thZ2VzL0JvcnV0YS9pbmRleC5odG1sKSBSIHBhY2thZ2UgKHYuNi4wLjApLiBXZSBpbXBsZW1lbnRlZCB0aGUgQm9ydXRhIHBlcm11YXRhaW9ucyBtZXRob2Qgd2l0aCBhIGNvbnNlbnN1cyByYW5rIGltcG9ydGFuY2UgbWV0cmljLCBhbmQgY29uZHVjdGVkIGJvb3RzdHJhcHMgb2YgZGF0YSBzdWJzZXQgc2VsZWN0aW9uICgyLzNyZHMgb2YgZGF0YSwgdG8gc2ltdWxhdGUgaXRlcmF0aXZlbHkgcmVkcmF3IG9mIHRyYWluaW5nIHNhbXBsZSBzdWJzZXQpLiBFYWNoIEJvcnV0YSBpdGVyYXRpb24gd2FzIGFsbG93ZWQgdG8gcnVuIGZvciB1cCB0byAxMDAgc3RlcHMsIG92ZXIgd2hpY2ggdGhlIGFsZ29yaXRobSBkZXNpZ25hdGVkICJjb25maXJtZWQiLCAidGVudGF0aXZlIiwgYW5kICJyZWplY3RlZCIgZmVhdHVyZXMuCgpIeXBlcnBhcmFtZXRlciBzZXRzIHVzZWQgZm9yIGFsZ29yaXRobSB3aXRoIEJvcnV0YSBwZXJtdWF0YXRpb25zIHdlcmUgaW5mb3JtZWQgYnkgcHJlbGltaW5hcnkgaW52ZXN0aWdhdGlvbiBvZiBtb2RlbCBwZXJmb3JtYW5jZXMgYWNyb3NzIGh5cGVycGFyYW1ldGVyIHNldHMgZm9yIGVhY2ggYWxnb3JpdGhtLiBUaGUgaW5pdGlhbCBkZWZpbmVkIHRyYWluaW5nIGFuZCB0ZXN0IGRhdGEgc3Vic2V0cywgYXMgdXNlZCB0byBtZWFzdXJlIGRpZmZlcmVudGlhbCBnZW5lIGV4cHJlc3Npb24sIHdlcmUgdXNlZCBpbiBoeXBlcnBhcmFtZXRlciBvcHRpbWl6YXRpb24gYW5kIHRvIGRlcml2ZSB0aGUgcmFuay1iYXNlZCBjb25zZW5zdXMgaW1wb3J0YW5jZSBtZWFzdXJlIGFzIGRlc2NyaWJlZCBiZWxvdy4gCgojIyBDb25zZW5zdXMgSW1wb3J0YW5jZSAoJ25yYW5rJykKClRvIGNhbGN1bGF0ZSBhIGNvbnNlbnN1cyBpbXBvcnRhbmNlIG1ldHJpYywgd2UgZGVmaW5lIGEgbWV0aG9kIHRvIHRha2UgdGhlIG1lZGlhbiBub3JtYWxpemVkIGFic29sdXRlIHJhbmsgb2YgZmVhdHVyZXMgZnJvbSBhY3Jvc3MgNCBhbGdvcml0aG1zIChsYXNzbywgWEdCb29zdCwgUmFuZG9tIEZvcmVzdCwgYW5kIFNWTSkuCgpTdGVwcyB0byBjYWxjdWxhdGUgdGhpcyBub3JtYWxpemVkIG1lZGlhbiBpbXBvcnRhbmNlIGluY2x1ZGU6CgoxLiBDYWxjdWxhdGUgYWxnb3JpdGhtLXNwZWNpZmljIGltcG9ydGFuY2VzLgoyLiBUYWtlIGFic29sdXRlIGltcG9ydGFuY2VzIGZyb20gKDEpLgozLiBDYWxjdWxhdGUgbmFpdmUgcmFuayAoaW5kZXgtYmFzZWQpIG9mIGltcG9ydGFuY2VzIGZyb20gKDIpLgo0LiBDYWxjdWFsdGUgbm9ybWFsaXplZCByYW5rIGZyb20gKDMpLgo1LiBDYWxjdWxhdGUgbWVkaWFuIG5vcm1hbGl6ZWQgcmFuayBhbmQgcmV0dXJuLgoKV2Ugc2V0dGxlZCBvbiB0aGlzIHN0cmF0ZWd5IGR1ZSB0byBwcm9wZXJ0aWVzIG9mIEJvcnV0YSBhbmQgZmVhdHVyZSBzZWxlY3Rpb24uIEZvciBjb21wYXJpc29uLCBhIHN0YW5kYXJkIG9mIEJvcnV0YSB1c2luZyBSYW5kb20gRm9yZXN0IGltcG9ydGFuY2Ugc2hvd3Mgb3NjaWxsYXRpb24gb2Ygc2hhZG93IGZlYXR1cmUgaW1wb3J0YW5jZXMsIGdyYWR1YWwgZXhjbHVzaW9uIG9mIHJlamVjdGVkIGZlYXR1cmVzLCBhbmQgcmV0ZW50aW9uIG9mIGltcG9ydGFudCBmZWF0dXJlcyAoRmlndXJlIDEpIAoKIVtIaXN0b3J5IG9mIHNoYWRvdyBmZWF0dXJlIGltcG9ydGFuY2VzIG92ZXIgcGVybXVhdGF0aW9ucyBpbiBhIHNpbmdsZSBCb3J1dGEgaXRlcmF0aW9uIHVzaW5nIFJhbmRvbSBGb3Jlc3QgaW1wb3J0YW5jZSAoZ3JlZW46IGNvbmZpcm1lZCBmZWF0dXJlcywgcmVkOiByZWplY3RlZCBmZWF0dXJlcywgeWVsbG93OiB0ZW50YXRpdmUgZmVhdHVyZXMpLl0oYnJmX2ltcGhpc3RfbGluZXBsb3QuanBlZykKCkJ5IGNvbnRyYXN0LCB1c2luZyBhIG5haXZlIG1lZGlhbiByYW5rIGFzIG91ciBjb25zZW5zdXMgaW1wb3J0YW5jZSB5aWVsZHMgYSBzdGF0aWMgcGF0dGVybiBvZiBzaGFkb3cgZmVhdHVyZSBpbXBvcnRhbmNlIGFjcm9zcyBwZXJtdXRhdGlvbnMgKEZpZ3VyZSAyKS4KCiFbSGlzdG9yeSBvZiBzaGFkb3cgZmVhdHVyZSBpbXBvcnRhbmNlIG92ZXIgQm9ydXRhIHBlcm11dGF0aW9ucyB1c2luZyBuYWl2ZSBtZWRpYW4gcmFuayBhcyBjb25zZW5zdXMgaW1wb3J0YW5jZSAoZ3JlZW46IGNvbmZpcm1lZDsgcmVkOiByZWplY3RlZCkuXShib3J1dGFoaXN0X25haXZlbWVkaWFucmFuay5wbmcpCgpUaGUgc3RhdGljIG5hdHVyZSBvZiBuYWl2ZSByYW5rIGlzIGFsbW9zdCBjZXJ0YWlubHkgZHVlIHRvIGltbWVkaWF0ZSBmaXhhdGlvbiBvZiBmZWF0dXJlIGNvbnNlbnN1cyBpbXBvcnRhbmNlIGZyb20gdGhlIGZpcnN0IGl0ZXJhdGlvbi4gVGhpcyBpcyBsaWtlbHkgYmVjYXVzZSBuYWl2ZSByYW5rIGlzIG5vdCBub3JtYWxpemVkLCBhbmQgZm9yIHBlbmFsaXplZCBhbGdvcml0aG1zIChYR0Jvb3N0IGFuZCBsYXNzbyksIGl0IHJldHVybnMgdmVyeSBsb3cgcmFuayBmb3IgbW9zdCBmZWF0dXJlcy4gVGhlc2UgY2hhcmFjdGVyaXN0aWNzIG1ha2UgdGhpcyBtZXRyaWMgbGVzcyBkZXNyaWFibGUgZm9yIHVzZSBpbiBCb3J1dGEgcGVybXV0YXRpb25zLCBhcyBpbXBvcnRhbmNlIGVzdGltYXRpb24gZG9lcyBub3QgYmVuZWZpdCBmcm9tIHNoYWRvdyBmZWF0dXJlIGltcG9ydGFuY2UgYW5kIGJhY2tncm91bmQgZXN0aW1hdGlvbi4KClVzaW5nIHRoZSBzdGVwcyBkZXNjcmliZWQgYWJvdmUsIHdlIGNhbGN1bGF0ZWQgYSBub3JtYWxpemVkIG1lZGlhbiByYW5rIGZvciB0aGUgY29uc2Vuc3VzIGltcG9ydGFuY2Ugd2UgdWx0aW1hdGVseSB1c2VkIHRvIGlkZW50aWZ5IGNvbnNlbnN1cyBpbXBvcnRhbnQgZmVhdHVyZXMuIEEgc2luZ2xlIEJvcnV0YSBpdGVyYXRpb24gdXNpbmcgdGhpcyBtZXRyaWMgc2hvd3MgcHJvZ3Jlc3NpdmUgcmV0ZW50aW9uIG9mICJjb25maXJtZWQiIGFuZCAidGVudGF0aXZlIiBmZWF0dXJlcywgYW5kIGxvc3Mgb2YgInJlamVjdGVkIiBmZWF0dXJlcyBvdmVyIHBlcm11dGF0aW9ucywgaW5kaWNhdGluZyB0aGlzIG1ldHJpYyBkb2VzIGJlbmVmaXQgZnJvbSBzaGFkb3cgZmVhdHVyZSBpdGVyYXRpb25zIChGaWd1cmUgMykuCgohW0hpc3Rvcnkgb2Ygc2hhZG93IGZlYXR1cmUgaW1wb3J0YW5jZSB3aXRoIG5vcm1hbGl6ZWQgbWVkaWFuIHJhbmsgdXNlZCB0byBjYWxjdWxhdGUgY29uc2Vuc3VzIGltcG9ydGFuY2UgKGdyZWVuOiBjb25maXJtZWQ7IHJlZDogcmVqZWN0ZWQ7IHllbGxvdzogdGVudGF0aXZlKV0oYm9ydXRhaXRlci1pbXBoaXN0X25yYW5rLmpwZWcpCgpDb21wYXJpbmcgY29uc2Vuc3VzIGltcG9ydGFuY2UgZGVyaXZlZCBmcm9tIG5haXZlIG1lZGlhbiByYW5rIGFuZCBub3JtYWxpemVkIG1lZGlhbiByYW5rIGRpcmVjdGx5LCB0aGVyZSBpcyBncmVhdGVyIHZhcmlhdGlvbiBpbiBpbXBvcnRhbmNlIG1lYXN1cmVkIHVzaW5nIHRoZSBsYXR0ZXIgKEZpZ3VyZSA0KS4KCiFbQ29tcGFyaXNvbiBvZiBtZWRpYW4gcmFuayBtZWFzdXJlcyAobmFpdmUgdnMuIG5vcm1hbGl6ZWQpIGFjcm9zcyA0IGFsZ29yaXRobXMgKGxhc3NvOiBncmVlbiwgWEdCb29zdDogYmx1ZSwgUmFuZG9tIEZvcmVzdDogb3JhbmdlLCBhbmQgU1ZNOiByZWQpLiBdKHJhbmtjb21wYXJlXzRhbGdvLmpwZykKCiMjIEJvb3RzdHJhcHBpbmcgQm9ydXRhIFBlcm11dGF0aW9ucwoKV2UgcGVyZm9ybWVkIDEwMDAgYm9vdHN0cmFwcyBvZiBCb3J1dGEgcGVybXV0YXRpb25zIGZvciBlYWNoIG9mIGZpdmUgcmVzcGVjdGl2ZSBpbXBvcnRhbmNlIG1ldHJpY3MuIEVhY2ggYm9vdHN0cmFwIHJlZHJldyB0d28gdGhpcmRzIG9mIHRoZSBkYXRhc2V0LCB3aXRoIHByZXNlcnZhdGlvbiBvZiBzYW1wbGUgZ3JvdXAgZnJlcXVlbmN5IHRvIG92ZXJhbGwgZnJlcXVlbmN5LiBUaGlzIHdhcyB0byBzaW11bGF0ZSByZWRyYXdpbmcgdHJhaW5pbmcgZGF0YSBzdWJzZXRzLiBUaGUgaW1wb3J0YW5jZSBtZXRyaWNzIGFwcGxpZWQgaW5jbHVkZWQ6CgoxLiBDb25zZW5zdXMgaW1wb3J0YW5jZSAobm9ybWFsaXplZCBtZWRpYW4gYWJzb2x1dGUgcmFuaywgc2VlIGFib3ZlKS4KMi4gTGFzc28gaW1wb3J0YW5jZSAoQmV0YS12YWx1ZSBjb2VmZmljaWVudCkuCjMuIFhHQm9vc3QgaW1wb3J0YW5jZSAoZmVhdHVyZSBpbXBvcnRhbmNlKS4KNC4gUmFuZG9tIEZvcmVzdCBJbXBvcnRhbmNlIChmZWF0dXJlIGltcG9ydGFuY2UpLgo1LiBTVk0gSW1wb3J0YW5jZSAoZmVhdHVyZSB3ZWlnaHQpLgoKQ29kZSBmb3IgcnVubmluZyBib290c3RyYXBzIGlzIGRlc2NyaWJlZCBiZWxvdy4KCkltcG9ydGFuY2UgbWV0cmljIGZ1bmN0aW9ucyB3ZXJlIGRlZmluZWQgYXMgZm9sbG93czoKYGBge3IsIGltcE1ldHJpY3N9CgojIEltcG9ydGFuY2UgRnVuY3Rpb25zCiAgaW1wTGFzc28gPC0gZnVuY3Rpb24oZGYsIGNsYXNzZXMsIHRyYWluaW5kaWNlcywgc2VlZD0yMDE5KXsKICAgICMgZGYgOiBkYXRhIGZyYW1lIHRvIHBhcnNlLCByb3duYW1lcyA9IGNsYXNzaWZpZXIgZ3JvdXBpbmdzLCBjb2xuYW1lcyA9IGZlYXR1cmUgaWRzCiAgICByZXF1aXJlKGdsbW5ldCkKICAgIHJlcXVpcmUoU3VtbWFyaXplZEV4cGVyaW1lbnQpCiAgICBzZXQuc2VlZChzZWVkKSAKICAgIHZhci5jbGFzc2lmaWVyIDwtIHJlc3BvbnNlIDwtIGFzLmNoYXJhY3RlcihjbGFzc2VzKQogICAgeSA8LSBmYWN0b3IocmVzcG9uc2UpOyBuYW1lcyh5KSA8LSByb3duYW1lcyhkZikgIyByZXNwb25zZSB2YXIgb2JqCiAgICB4ID0gZGYgIyBnZW5lcyBvZiBpbnRlcmVzdAogICAgY29udHJhc3QgPC0gY29udHJhc3RzKHkpCiAgICBncmlkIDwtIDEwXiBzZXEoMTAsLTIsIGxlbmd0aD0xMDApCiAgICAKICAgICMgdXNlIGNyb3NzLXZhbGlkYXRpb24gb24gdGhlIHRyYWluaW5nIG1vZGVsLkNWIG9ubHkgZm9yIGxhbWJkYQogICAgbWVzc2FnZSgicGVyZm9ybWluZyBjcm9zcy12YWxpZGF0aW9uLi4uIikKICAgIGN2LmZpdCA8LSBjdi5nbG1uZXQoeFt0cmFpbmluZGljZXMsXSwgeVt0cmFpbmluZGljZXNdLCBmYW1pbHkgPSAiYmlub21pYWwiLAogICAgICAgICAgICAgICAgICAgICAgICB0eXBlLmxvZ2lzdGljPSJtb2RpZmllZC5OZXd0b24iLCBzdGFuZGFyZGl6ZSA9IEZBTFNFLAogICAgICAgICAgICAgICAgICAgICAgICBsYW1iZGEgPSBncmlkLCBhbHBoYT0xLCBuZm9sZHMgPSBsZW5ndGgodHJhaW5pbmRpY2VzKSwgI0xPT0NWIAogICAgICAgICAgICAgICAgICAgICAgICB0eXBlLm1lYXN1cmUgPSAiY2xhc3MiLCBpbnRlcmNlcHQgPSBGQUxTRSkKICAgICNTZWxlY3QgbGFtYmRhIG1pbi4KICAgIG1lc3NhZ2UoInNlbGVjdGluZyBsYW1iZGEgbWluLi4uIikKICAgIGxhbWJkYS5taW4gPC0gY3YuZml0JGxhbWJkYS5taW4KICAgIAogICAgI0ZpdCB0aGUgZnVsbCBkYXRhc2V0LgogICAgbWVzc2FnZSgiZml0dGluZyB3aG9sZSBkYXRhc2V0IikKICAgIGxhc3NvZml0IDwtIGdsbW5ldCh4LCB5LCBmYW1pbHkgPSAiYmlub21pYWwiLCBzdGFuZGFyZGl6ZSA9IEZBTFNFLCAKICAgICAgICAgICAgICAgICAgICAgICBsYW1iZGEgPSBncmlkLCBhbHBoYSA9IDEsIGludGVyY2VwdCA9IEZBTFNFKQogICAgCiAgICAjRXh0cmFjdCB0aGUgY29lZmZpY2llbnRzCiAgICBsYXNzb2ltcCA8LSBwcmVkaWN0KGxhc3NvZml0LCB0eXBlPSJjb2VmZmljaWVudHMiLCBzPWxhbWJkYS5taW4pCiAgICBsYXNzb2ltcCA8LSBsYXNzb2ltcFsyOm5yb3cobGFzc29pbXApLDFdCiAgICByZXR1cm4obGFzc29pbXApCiAgfQogIGltcFJGIDwtIGZ1bmN0aW9uKGRmLCBjbGFzc2VzLCBudHJlZXM9MTAwLCBzZWVkPTIwMTkpewogICAgcmVxdWlyZShyYW5kb21Gb3Jlc3QpCiAgICBzZXQuc2VlZChzZWVkKQogICAgY2xhc3MgPC0gYXMubnVtZXJpYyhjbGFzc2VzKQogICAgcmZmaXQgPC0gcmFuZG9tRm9yZXN0KGNsYXNzIH4gLiwgZGF0YSA9IGFzLm1hdHJpeChkZiksIG50cmVlID0gbnRyZWVzLHByb3hpbWl0eSA9IFRSVUUpCiAgICAjIHJmaW1wIDwtIGFzLm51bWVyaWMoZ2V0UkZJdmFyKHJmbW9kZWw9cmZmaXQpKQogICAgcmZpbXAgPC0gaW1wb3J0YW5jZShyZmZpdClbLDFdCiAgICByZXR1cm4ocmZpbXApCiAgfQogIGltcFhHQiA8LSBmdW5jdGlvbihkZiwgY2xhc3Nlcywgc2VlZD0yMDE5KXsKICAgIHJlcXVpcmUoeGdib29zdCkKICAgIHNldC5zZWVkKDIwMTkpCiAgICBtZXNzYWdlKCJmaXR0aW5nIHhnYm9vc3QgbW9kZWwuLi4iKQogICAgeGdiZml0IDwtIHhnYm9vc3QoZGF0YSA9IGRmLCBsYWJlbCA9IGNsYXNzZXMsIG1heF9kZXB0aCA9IDIsCiAgICAgICAgICAgICAgICAgICAgICBldGEgPSAxLCBudGhyZWFkID0gMiwgbnJvdW5kcyA9IDIsIG9iamVjdGl2ZSA9ICJiaW5hcnk6bG9naXN0aWMiKQogICAgbWVzc2FnZSgiZ2V0dGluZyB4Z2Jvb3N0IGltcG9ydGFuY2VzLi4uIikKICAgIHhnYmltcCA8LSB4Z2IuaW1wb3J0YW5jZShmZWF0dXJlX25hbWVzID0gY29sbmFtZXMoZGYpLCBtb2RlbCA9IHhnYmZpdCkKICAgIG1lc3NhZ2UoInJlZm9ybWF0dGluZyB4Z2IgaW1wb3J0YW5jZXMuLi4iKQogICAgCiAgICB4Z2JpbXAuZm9ybWF0IDwtIGMocmVwKDAsIG5jb2woZGYpKSkKICAgIG5hbWVzKHhnYmltcC5mb3JtYXQpIDwtIGNvbG5hbWVzKGRmKQogICAgZm9yKGYgaW4gMTpucm93KHhnYmltcCkpewogICAgICB4Z2JpbXAuZm9ybWF0W3doaWNoKGNvbG5hbWVzKGRmKT09YXMuY2hhcmFjdGVyKHhnYmltcFtmLDFdKSldIDwtIGFzLm51bWVyaWMoeGdiaW1wW2YsMl0pCiAgICB9CiAgICB4Z2JpbXAuZm9ybWF0IDwtIGFzLm51bWVyaWMoeGdiaW1wLmZvcm1hdCkKICAgIG5hbWVzKHhnYmltcC5mb3JtYXQpIDwtIGNvbG5hbWVzKGRmKQogICAgCiAgICByZXR1cm4oeGdiaW1wLmZvcm1hdCkKICB9CiAgaW1wU1ZNIDwtIGZ1bmN0aW9uKGRmLCBjbGFzc2VzLCBzZWVkPTIwMTkpewogICAgcmVxdWlyZShlMTA3MSkKICAgIHNldC5zZWVkKDIwMTkpCiAgICBtZXNzYWdlKCJmaXR0aW5nIHN2bSBtb2RlbC4uLiIpCiAgICBzdm1maXQgPC0gc3ZtKGFzLmZhY3RvcihjbGFzc2VzKX4uLCAKICAgICAgICAgICAgICAgICAgZGF0YT1kZiwgCiAgICAgICAgICAgICAgICAgIG1ldGhvZD0iQy1jbGFzc2lmaWNhdGlvbiIsIAogICAgICAgICAgICAgICAgICBrZXJuZWw9ImxpbmVhciIpCiAgICBzdm1pbXAgPC0gIHQoc3ZtZml0JGNvZWZzKSAlKiUgc3ZtZml0JFNWCiAgICBtZXNzYWdlKCJyZWZvcm1hdHRpbmcgaW1wb3J0YW5jZXMgZm9yIG91dHB1dC4uLiIpCiAgICBzdm1pbXAuZm9ybWF0IDwtIHN2bWltcFsxLF0KICAgIG5hbWVzKHN2bWltcC5mb3JtYXQpIDwtIGNvbG5hbWVzKHN2bWltcCkKICAgIHJldHVybihzdm1pbXAuZm9ybWF0KQogIH0KICAjIENNTCBmb3IgQm9ydXRhIEltcGxlbWVudGF0aW9uCiAgaW1wQm9ydXRhQ01MIDwtIGZ1bmN0aW9uKHg9eCwgeT15LCBzZWVkLCByYW5rc3VtbWFyeT0ibWVkaWFuIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgYWxnby5vcHQ9YygibGFzc28iLCJyZiIsInN2bSIsInhnYiIpKXsKICAgICMgaW1wQ01MCiAgICAjIEdldCBjb25zZW5zdXMgaW1wb3J0YW5jZSByYW5rcyBmcm9tIGRpc3BhcmF0ZSBhbGdvcml0aG1zLgogICAgIyBBcmd1bWVudHMKICAgICMgKiBkZiAobWF0cml4KSA6IEVudGlyZSBkYXRhc2V0IG1hdHJpeCAocm93cyA9IGluc3RhbmNlcywgY29sdW1ucyA9IGZlYXR1cmVzKQogICAgIyAqIGNsYXNzZXMgKGNoYXJhY3Rlcik6IGNhdGVnb3JpemF0aW9ucyBvZiBpbnN0YW5jZXMKICAgICMgKiBhbGdvLm9wdCAobGlzdCk6IExpc3Qgb2YgdmFsaWQgYWxnb3JpdGhtcyB0byB1c2UgZm9yIGNvbnNlbnN1cwogICAgIyAqIHNlZWQgKGludCk6IFNldCB0aGUgc2VlZCBmb3IgcmVwcm9kdWNpYmlsaXR5CiAgICAjICogcmFua3N1bW1hcnkgKHN0cmluZyk6IEVpdGhlciAic2NvcmUiLCAibWVkaWFuIiwgb3IgIm1lYW4iLCB0aGUgb3BlcmF0aW9uIHVzZWQgdG8gY2FsY3VsYXRlIGNvbnNlbnN1cyByYW5rLgogICAgIyBSZXR1cm5zOgogICAgIyAqIENvbnNlbnN1cyByYW5rLCBvcHRpb25hbGx5IGEgc3RhbmRhcmQgb3V0cHV0IHRhYmxlIG9mIGltcG9ydGFuY2VzIGZvciBzZWxlY3RlZCBhbGdvcml0aG1zIChpZiBzdGFuZHRhYmxlPT1UUlVFKSAKICAgIAogICAgIyBkZWZpbmUgdGhlIHRlc3QgZGYgaWYgcHJvdmlkZWQgb3IgaWYgRkFMU0UKICAgIGRmLnRlc3QgPC0gYXMubWF0cml4KHgpCiAgICBtZXNzYWdlKCJwcm9jZWVkaW5nIHdpdGggZGYgb2Ygc2l6ZSAiLG5yb3coZGYudGVzdCkpCiAgICBjbGFzc2VzIDwtIHkKICAgIHByaW50KCJnZXR0aW5nIGltcG9ydGFuY2VzLi4uIikKICAgIGltcGxpc3QgPC0gbGlzdCgpCiAgICBpbXBsYWJlbGxpc3QgPC0gYygpCiAgICAKICAgIGlmKCJsYXNzbyIgJWluJSBhbGdvLm9wdCl7CiAgICAgICMgZGVmaW5lIHRoZSB0cmFpbmluZGljZXMgaWYgbm9uZSBwcm92aWRlZCBvciBGQUxTRQogICAgICBtZXNzYWdlKCJwZXJmb3JtaW5nIGxhc3NvLi4uIikKICAgICAgaW1wLmxhc3NvIDwtIGltcExhc3NvKGRmPWFzLm1hdHJpeChkZi50ZXN0KSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0cmFpbmluZGljZXM9c2VxKDEsbnJvdyhkZi50ZXN0KSksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgY2xhc3Nlcz1jbGFzc2VzKQogICAgICBpbXBsaXN0W1sibGFzc28iXV0gPC0gaW1wLmxhc3NvCiAgICAgIGltcGxhYmVsbGlzdCA8LSBjKGltcGxhYmVsbGlzdCwgImxhc3NvIikKICAgIH0KICAgIGlmKCJyZiIgJWluJSBhbGdvLm9wdCl7CiAgICAgIGltcC5yZiA8LSBpbXBSRihkZj1hcy5tYXRyaXgoZGYudGVzdCksIGNsYXNzZXM9Y2xhc3NlcykKICAgICAgaW1wbGlzdFtbInJmIl1dIDwtIGltcC5yZgogICAgICBpbXBsYWJlbGxpc3QgPC0gYyhpbXBsYWJlbGxpc3QsICJyZiIpCiAgICB9CiAgICBpZigieGdiIiAlaW4lIGFsZ28ub3B0KXsKICAgICAgaW1wLnhnYiA8LSBpbXBYR0IoZGY9YXMubWF0cml4KGRmLnRlc3QpLCBjbGFzc2VzPWNsYXNzZXMpCiAgICAgIGltcGxpc3RbWyJ4Z2IiXV0gPC0gaW1wLnhnYgogICAgICBpbXBsYWJlbGxpc3QgPC0gYyhpbXBsYWJlbGxpc3QsICJ4Z2IiKQogICAgfQogICAgaWYoInN2bSIgJWluJSBhbGdvLm9wdCl7CiAgICAgIGltcC5zdm0gPC0gaW1wU1ZNKGRmPWFzLm1hdHJpeChkZi50ZXN0KSwgY2xhc3Nlcz1jbGFzc2VzKQogICAgICBpbXBsaXN0W1sic3ZtIl1dIDwtIGltcC5zdm0KICAgICAgaW1wbGFiZWxsaXN0IDwtIGMoaW1wbGFiZWxsaXN0LCAic3ZtIikKICAgIH0KICAgICMgbWF0Y2ggaW1wb3J0YW5jZSBmZWF0dXJlIGxhYmVsIG9yZGVyaW5nCiAgICBpZihsZW5ndGgoaW1wbGlzdCk+MSl7CiAgICAgIGZvcihpIGluIDE6KGxlbmd0aChpbXBsaXN0KS0xKSl7CiAgICAgICAgaW1wbGlzdFtbaV1dIDwtIGltcGxpc3RbW2ldXVtvcmRlcihtYXRjaChuYW1lcyhpbXBsaXN0W1tpXV0pLG5hbWVzKGltcGxpc3RbW2krMV1dKSkpXQogICAgICB9CiAgICB9CiAgICAKICAgICMgZ2V0IGltcG9ydGFuY2UgcmFua3MgYW5kIHJhbmt2YXJzCiAgICBpZihyYW5rc3VtbWFyeSAlaW4lIGMoIm1lZGlhbiIsIm1lYW4iKSl7CiAgICAgIGltcHJhbmtsaXN0IDwtIGxpc3QoKQogICAgICAjIGZvciBlYWNoIHJhbmssIGNhbGN1bGF0ZSBub3JtYWxpemVkIHJhbmsgcG9zaXRpb24KICAgICAgbWVzc2FnZSgiY29tcHV0aW5nIG5vcm1hbGl6ZWQgcmFuayBpbXBvcnRhbmNlcy4uLiIpCiAgICAgIGZvcihpIGluIDE6bGVuZ3RoKGltcGxpc3QpKXsKICAgICAgICBhbGdvbmFtZSA8LSBuYW1lcyhpbXBsaXN0KVtpXQogICAgICAgIGltcHZhbHMgPC0gaW1wbGlzdFtbaV1dCiAgICAgICAgIyBuYWl2ZSByYW5rCiAgICAgICAgbnJhbmtpIDwtIHJhbmsoYWJzKGltcHZhbHMpKQogICAgICAgICMgYWRqMTogY29tcHJlc3MgcmFuayBsb3dlciBib3VuZHMKICAgICAgICBtaW4ucmFua2kgPC0gbWluKG5yYW5raSkKICAgICAgICBucmFua2kxIDwtIG5yYW5raQogICAgICAgIG5yYW5raTFbbnJhbmtpMT09bWluLnJhbmtpXSA8LSBtaW4obnJhbmtpMVshbnJhbmtpMT09bWluLnJhbmtpXSktMQogICAgICAgICMgYWRqMjogbm9ybWFsaXplIHJhbmsgc2NhbGUgKGRpZi5taW4vcmFuZ2UpCiAgICAgICAgbnJhbmtpMiA8LSBucmFua2kxCiAgICAgICAgbnJhbmtpMiA8LSAobnJhbmtpMi1taW4obnJhbmtpMikpLyhtYXgobnJhbmtpMiktbWluKG5yYW5raTIpKQogICAgICAgICMgYWx3YXlzIGNvbXB1dGUgYWJzb2x1dGUgcmFua3MKICAgICAgICBpbXByYW5rbGlzdFtbYWxnb25hbWVdXSA8LSBucmFua2kyCiAgICAgICAgIyBwbG90KGltcHZhbHMsIG5yYW5raSwgbWFpbj1hbGdvbmFtZSkKICAgICAgICAjIHBsb3QoaW1wdmFscywgbnJhbmtpMSwgbWFpbj1hbGdvbmFtZSkKICAgICAgICAjIHBsb3QoaW1wdmFscywgbnJhbmtpMiwgbWFpbj1hbGdvbmFtZSkKICAgICAgfQogICAgICBtZWRyYW5rIDwtIGMoKQogICAgICBtZWFucmFuayA8LSBjKCkKICAgICAgIyBpdGVyYXRlIG9uIGZlYXR1cmVzCiAgICAgIGZvcihyIGluIDE6bmNvbCh4KSl7CiAgICAgICAgcnZhbHIgPC0gYygpICMgZ2V0IGZlYXR1cmUtbGV2ZWwgcmFua3MKICAgICAgICBmb3IoaSBpbiAxOmxlbmd0aChpbXByYW5rbGlzdCkpewogICAgICAgICAgcnZhbHIgPC0gYyhydmFsciwgaW1wcmFua2xpc3RbW2ldXVtyXSkgIyBhcHBlbmQgcmFua3MKICAgICAgICB9CiAgICAgICAgIyBhcHBlbmQgc3VtbWFyaXplZCBmZWF0dXJlLWxldmVsIHJhbmtzLCB0byByZXR1cm4KICAgICAgICBtZWRyYW5rIDwtIGMobWVkcmFuaywgbWVkaWFuKHJ2YWxyKSkKICAgICAgICBtZWFucmFuayA8LSBjKG1lYW5yYW5rLCBtZWFuKHJ2YWxyKSkKICAgICAgfQogICAgICAjIGZpbmFsIGltcG9ydGFuY2UgdmFsdWUgaXMgZGlyZWN0bHkgcHJvcG9ydGlvbmFsIHRvIHN1bW1hcml6ZWQgcmFuawogICAgICBpZihyYW5rc3VtbWFyeT09Im1lZGlhbiIpewogICAgICAgIGxyIDwtIG1lZHJhbmsKICAgICAgfSBlbHNlewogICAgICAgIGxyIDwtIG1lYW5yYW5rCiAgICAgIH0KICAgICAgbWVzc2FnZSgiY29tcGxldGVkIGFsbCB0YXNrcyEgUmV0dXJuaW5nLi4uIikKICAgICAgbHIKICAgICAgcmV0dXJuKGxyKQogICAgfQogICAgCiAgICAjIGdldCBzY29yZSBpbXBvcnRhbmNlIG1ldHJpYwogICAgaWYocmFua3N1bW1hcnk9PSJzY29yZSIpewogICAgICAjIG5vdGVzOiBieS1hbGdvIHNjb3JlIGNyaXRlcmlhCiAgICAgICMgbGFzc28sIGNvZWZmIT0wCiAgICAgICMgcmYsIGltcD49OTB0aCBxdWFudGlsZQogICAgICAjIHN2bSwgYWJzLXdlaWdodCA+PSA5MHRoIHF1YW50aWxlCiAgICAgICMgeGdiLCBjb2VmZiAhPSAwCiAgICAgIGZlYXRuYW1lcyA8LSBjb2xuYW1lcyh4KQogICAgICBpbXBzY29yZSA8LSByZXAoMCxsZW5ndGgoZmVhdG5hbWVzKSkKICAgICAgbmFtZXMoaW1wc2NvcmUpIDwtIGNvbG5hbWVzKHgpCiAgICAgIGZvcihpIGluIDE6bGVuZ3RoKGltcGxpc3QpKXsKICAgICAgICBuaSA8LSBuYW1lcyhpbXBsaXN0KVtpXQogICAgICAgIGlmKG5pPT0ibGFzc28iKXsKICAgICAgICAgIHdoaWNoLmZlYXR1cmVzIDwtIG5hbWVzKGltcGxpc3RbW2ldXVtpbXBsaXN0W1tpXV0hPTBdKQogICAgICAgICAgaW1wc2NvcmVbd2hpY2guZmVhdHVyZXNdIDwtIGltcHNjb3JlW3doaWNoLmZlYXR1cmVzXSsxCiAgICAgICAgfQogICAgICAgIGlmKG5pPT0ieGdiIil7CiAgICAgICAgICB3aGljaC5mZWF0dXJlcyA8LSBuYW1lcyhpbXBsaXN0W1tpXV1baW1wbGlzdFtbaV1dIT0wXSkKICAgICAgICAgIGltcHNjb3JlW3doaWNoLmZlYXR1cmVzXSA8LSBpbXBzY29yZVt3aGljaC5mZWF0dXJlc10rMQogICAgICAgIH0KICAgICAgICBpZihuaT09InJmIil7CiAgICAgICAgICBxcmYgPC0gYXMubnVtZXJpYyhxdWFudGlsZShhcy5udW1lcmljKGltcGxpc3RbW2ldXSksIHNlcSgwLDEsMC4xKSlbMTBdKQogICAgICAgICAgd2hpY2guZmVhdHVyZXMgPC0gbmFtZXMoaW1wbGlzdFtbaV1dW2ltcGxpc3RbW2ldXT49cXJmXSkKICAgICAgICAgIGltcHNjb3JlW3doaWNoLmZlYXR1cmVzXSA8LSBpbXBzY29yZVt3aGljaC5mZWF0dXJlc10rMQogICAgICAgIH0KICAgICAgICBpZihuaT09InN2bSIpewogICAgICAgICAgcXN2bSA8LSBhcy5udW1lcmljKHF1YW50aWxlKGFicyhhcy5udW1lcmljKGltcGxpc3RbW2ldXSkpLCBzZXEoMCwxLDAuMSkpWzEwXSkKICAgICAgICAgIHdoaWNoLmZlYXR1cmVzIDwtIG5hbWVzKGltcGxpc3RbW2ldXVthYnMoaW1wbGlzdFtbaV1dKT49cXN2bV0pCiAgICAgICAgICBpbXBzY29yZVt3aGljaC5mZWF0dXJlc10gPC0gaW1wc2NvcmVbd2hpY2guZmVhdHVyZXNdKzEKICAgICAgICB9CiAgICAgIH0KICAgICAgcnMgPC0gYXMubnVtZXJpYyhpbXBzY29yZSkKICAgICAgcnMKICAgICAgcmV0dXJuKHJzKQogICAgfQogICAgCiAgICByZXR1cm4oKQogIH0KCmBgYAoKIyBSZXN1bHRzIG9mIEJvcnV0YSBQZXJtdXRhdGlvbnMgQm9vdHN0cmFwcwoKQWZ0ZXIgcGVyZm9ybWluZyBib290c3RyYXBzIGFzIGRlc2NyaWJlZCwgd2UgYW5hbHl6ZWQgYW5kIHN1bW1hcml6ZWQgcmVzdWx0cy4gCgojIyBTdW1tYXJpZXMgQWNyb3NzIEltcG9ydGFuY2UgRnVuY3Rpb25zCgpXZSBvYnNlcnZlZCB0aGUgZm9sbG93aW5nIHJlc3VsdHMgZnJvbSBlYWNoIGJvb3RzdHJhcCBpdGVyYXRpb24gZW1wbG95aW5nIG9uZSBvZiB0aGUgZml2ZSBkZXNjcmliZWQgaW1wb3J0YW5jZSBtZWFzdXJlcy4KCiFbRmVhdHVyZSBjbGFzc2lmaWNhdGlvbiBzdW1tYXJ5IGFjcm9zcyBCb3J1dGEgQm9vdHN0cmFwcyB3aXRoIENvbnNlbnN1cyBpbXBvcnRhbmNlICgibnJhbmsiKS5dKGJicy1ucmFua19jb21wcGxvdC5qcGcpCiFbRmVhdHVyZSBjbGFzc2lmaWNhdGlvbiBzdW1tYXJ5IGFjcm9zcyBCb3J1dGEgQm9vdHN0cmFwcyB3aXRoIExhc3NvIGltcG9ydGFuY2UuXShiYnMtbGFzc29fY29tcHBsb3QuanBnKQohW0ZlYXR1cmUgY2xhc3NpZmljYXRpb24gc3VtbWFyeSBhY3Jvc3MgQm9ydXRhIEJvb3RzdHJhcHMgd2l0aCBSYW5kb20gRm9yZXN0IGltcG9ydGFuY2UuXShiYnMtcmZfY29tcHBsb3QuanBnKQohW0ZlYXR1cmUgY2xhc3NpZmljYXRpb24gc3VtbWFyeSBhY3Jvc3MgQm9ydXRhIEJvb3RzdHJhcHMgd2l0aCBTVk0gaW1wb3J0YW5jZS5dKGJicy1zdm1fY29tcHBsb3QuanBnKQohW0ZlYXR1cmUgY2xhc3NpZmljYXRpb24gc3VtbWFyeSBhY3Jvc3MgQm9ydXRhIEJvb3RzdHJhcHMgd2l0aCBYR0Jvb3N0IGltcG9ydGFuY2UuXShiYnMteGdiX2NvbXBwbG90LmpwZykKIyMgRmVhdHVyZSBJbXBvcnRhbmNlIEhpc3RvcmllcyBBY3Jvc3MgUnVucwoKQWNyb3NzIGJvb3RzdHJhcCBydW5zIHdpdGggdmFyeWluZyBpbXBvcnRhbmNlIG1ldHJpY3MsIHdlIG9ic2VydmVkIHRoZSBmb2xsb3dpbmcgcGF0dGVybnMgb2YgZmVhdHVyZSBpbXBvcnRuYWNlIGhpc3RvcmllcyBmcm9tIDQgYm9vdHN0cmFwcyBzZWxlY3RlZCBhdCByYW5kb20gZnJvbSBlYWNoIHJ1bi4KCiFbRmVhdHVyZSBoaXN0b3JpZXMgYWNyb3NzIEJvcnV0YSBwZXJtdXRhdGlvbnMsIGZyb20gNCBib290c3RyYXBzIGRyYXduIGF0IHJhbmRvbSBmcm9tIGVhY2ggb2YgdGhlIDUgcnVucyAoZ3JlZW4gPSBjb25maXJtZWQsIHJlZCA9IHJlamVjdGVkLCB5ZWxsb3cgPSB0ZW50YXRpdmUsIGJsdWUgbGluZXMgPSBzaGFkb3cgZmVhdHVyZSBtYXgsIG1lYW4sIGFuZCBtaW4pLl0oZmVhdGhpc3RfY29tcG9zaXRlXzVhbGdvLmpwZykKCiMjIE92ZXJsYXAgb2YgQ29uZmlybWVkIEZlYXR1cmVzCgpXZSBhbHNvIHN1bW1hcml6ZWQgdGhlIG92ZXJsYXAgaW4gY29uZmlybWVkIGFuZCByZWN1cnJlbnQgY29uZmlybWVkIGZlYXR1cmVzIGFjcm9zcyBib290c3RyYXAgcnVucy4gVGhlIGZvbGxvd2luZyB1cHNldCBwbG90cyBzaG93IHN1YnNldCBvdmVybGFwIG1lbWJlcnNoaXAgZm9yIGZlYXR1cmVzIGNvbmZpcm1lZCBhdCBsZWFzdCBvbmNlIGFjcm9zcyBib290c3RyYXBzLCBncmVhdGVyIHRoYXQgNSUgb2YgYm9vdHN0cmFwcywgb3IgZ3JlYXRlciB0aGFuIDIwJSBvZiBib290c3RyYXBzLgoKIVtGZWF0dXJlIG92ZXJsYXAgYW1vbmcgZmVhdHVyZXMgY29uZmlybWVkIGluIGF0IGxlYXN0IDEgYm9vdHN0cmFwLCBhY3Jvc3MgYm9vdHN0cmFwIHJ1bnMgd2l0aCA1IGltcG9ydGFuY2UgbWV0cmljcy5dKG5yYW5rLTRhbGdvX2djb25mYWxsX3Vwc2V0ci5qcGcpCgohW0ZlYXR1cmUgb3ZlcmxhcCBhbW9uZyBmZWF0dXJlcyBjb25maXJtZWQgaW4gYXQgbGVhc3QgNSUgb2YgYm9vdHN0cmFwIHJ1bnMsIGFjcm9zcyBib290c3RyYXAgcnVucyB3aXRoIDUgaW1wb3J0YW5jZSBtZXRyaWNzXShucmFuay00YWxnb19nY29uZjVwZXJjX3Vwc2V0ci5qcGcpCgohW0ZlYXR1cmUgb3ZlcmxhcCBhbW9uZyBmZWF0dXJlcyBjb25maXJtZWQgaW4gYXQgbGVhc3QgMjAlIG9mIGJvb3RzdHJhcCBydW5zLCBhY3Jvc3MgYm9vdHN0cmFwIHJ1bnMgd2l0aCA1IGltcG9ydGFuY2UgbWV0cmljc10obnJhbmstNGFsZ29fZ2NvbmYyMHBlcmNfdXBzZXRyLmpwZykKCg==